\documentclass[journal]{IEEEtran}
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{hyperref}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}

\begin{document}

\title{Algoritmos Evolutivos Paralelos aplicados al HSCP con restricciones de Deadline}
\author{Jonathan Muraña 4254556-7 \\Grupo 13 - Algoritmos Evolutivos\\ Facultad de Ingeniería, Universidad de la República\\Agosto, 2011 }

\maketitle

\begin{abstract}

En este documento se describen el problema HSCP,  su campo de aplicación, trabajos previos revisados, las particularidades de la versión considerada. También se plantean justificaciones sobre las distintas decisiones de diseño de los algoritmos, los principales operadores utilizados y un plan de experimentos a realizar.

\end{abstract}

\begin{keywords}
algoritmos evolutivos , HSCP, deadline
\end{keywords}

\section{Introducción}
Cuando es necesario procesar grandes volúmenes de datos o realizar calculos complejos se recurre a infraestructuras de hardware de gran porte como las costosas supercomputadoras, cluster de bajo costo o tecnologías grid. En todo caso, a pesar de que las velocidades están en el orden de los gigaflops, al momento de la ejecución de las tareas, no se logra explotar totalmente la capacidad del sistema si no se plantea una buena planificación. Se debe contar entonces con un scheduler que optimice los recursos de cómputo y además no genere demasiado overhead. En este trabajo se plantean planificadores basados en algoritmos evolutivos que mejoran las heurísticas clásicas para este problema considerando además el tiempo de finalización fijado para cada tarea.

\section{Trabajos previos relevantes}
Como trabajos previos se considera Nesmachnow 2010 en donde se trata el problema sin restricciones de deadline, utilizando algoritmos evolutivos para su resolución. Entre otros se plantea una versión paralela del algoritmo CHC que trabaja con poblaciones reducidas.

\section{Descripción de Problema}

El proyecto elegido pertenece al área de investigación operativa.  Se trata del problema conocido como HSCP (Heterogeneous Scheduling Computing Problem) en donde se busca encontrar una asignación de tareas en un determinado conjunto de máquinas de forma de minimizar algún objetivo. En general este objetivo es el tiempo total de ejecución o la espera del usuario, en caso de que se trate de un  servicio de cómputo. Otros objetivos a optimizar pueden ser la energía consumida, la violaciones en el tiempo estipulado para la ejecución de una tarea.\\
Como el problema es heterogeneo, las tareas no ejecutan en el mismo tiempo en cada máquina. En general habrá una máquina (la más potente de sistema) que ejecute todas las tareas más rápido que el resto, en este caso hablamos de un problema consistente, esto es precisamente que si una máquina A ejecuta una tarea más rápido que otra B, A ejecutará el resto de las tareas tambíen más rápido que B. Pero puede haber problemas en los cuales esto no se cumpla, ya sea por la diferencia en la arquitectura de las máquinas o por las características de las tareas. En este caso estamos ante un problema inconsistente (esta característica del problema es sumamente importante porque influye en la adecuación de la heurísticas utilizadas y por lo tanto en el propio AG).
Situando el planificador por ejemplo en un cluster paralelo, en un determinado momento se tienen N tareas, se planifican en los M procesadores y comienzan a ejecutar las que se asignaron primero. Luego se incorporan nuevas tareas a la espera. En este punto el panificador puede volver a planificar solo con las tareas que están en espera, o planificar considerando todas las tareas e interrumpir alguna tarea de las que ya están corriendo. En el caso de que se conozcan todas las tareas y tiempos de los trabajos, y que no se admitan nuevos trabajos, se trata de un escenario estático. Si el planificador conoce la información de las tareas a medida que arriban y replanifica en función de ella, se trata de un escenario dinámico. Además se podrian buscar predecir el comportamiento de los arribos y planificar tomando en cuenta esto, sería un planificador adaptativo.
Un planificador no preemtivo es aquel que no interrumpe las tareas luego de que se ponen en funcionamiento.
En este proyecto se ha optado por el modelo que se describe a continuación. Algunas decisiones se toman de forma de simplificar el problema y por considerar que si bien se alejan un poco de los planificadores reales, encierran la misma complejidad y comportamiento. Por ejemplo un scheduling dinámico se podría lograr aplicando el estático en cada arribo de tarea.
El escenario se considera estático, no preemtivo. La tareas no tienen precedencias o sea que son independientes y se pueden ejecutar en cualquier orden (son características de tareas de ambientes cientificos, como el cluster FING). Tampoco existen prioridades en las tareas. El objetivo es el makespan, que es el tiempo que se requiere para la finalización total y como restricción se tomará el deadline de cada trabajo, esto es, el máximo tiempo permitido para que finalice una determinada tarea.
¿Cuál es la duración de una tarea en cada máquina? 
La duración de una tarea puede depender de diversos factores y es imposible de saber de antemano. Se utiliza el modelo ETC (Expected time to compute Ali 2000) que consta de una matriz donde las filas representan las tareas y las columnas las máquinas.  A partir de parámetros de consistencia y heterogeneidad se sortean los valores de las entradas. 
Además para la estimación del deadline se utiliza un sorteo entre dos parámetros que se ajustan de modo que la instancia tenga solución. 

\subsection{Complejidad del problema}

Como es ampliamente conocido, el HSCP es NP difícil, la resolución por medio de métodos clásicos toma tiempo exponenciales, por lo tanto el problema es abordado (para instancias realistas y se se quiere realizar una planificación inteligente) mediante heurísticas y metaheurísticas.




\section{Área de aplicación}
En la actualidad la computación de alta velocidad está orientada a el procesamiento paralelo. Más precisamente a arquitecturas de tipo cluster y grids. La planificación en este contexto se vuelve un problema importante y más aún considerando las dimensiones (ciento de unidades de procesamiento). Cómo utilizar de forma óptima los recursos de cómputo es un cuello de botella a la hora de escalar los sitemas mencionados.


\section{Solución}

Con la finalidad de encontrar una solución de calidad al HSCP con restricciones de deadline, se planteará un algoritmo genético, además como es necesario reducir los tiempos de overhead del planificador, se implementará una versión paralela. El resultado de éste trabajo será:

\begin{enumerate}
\item Algorimo genético clásico serial para resolución de HSCP con restricciones de dealine.
\item Algoritmo CHC serial para resolución de HCSP con restricciones de deadline
\item Algorimo genético clásico paralelo para resolución de HSCP con restricciones de dealine.
\item Algoritmo CHC paralelo para resolución de HCSP con restricciones de deadline

\end{enumerate}



La decisión de implementar un algoritmo CHC parte de que se ha utilizado de forma satisfactoria para problemas de scheduling. Por ejemplo en Nesmachnov 2010 se atacó el problema sin restricciones. El algoritmo genético clasico se implementa con el fin de realizar comparaciones.
El primer problema a afrontar es generar instancias de prueba.Una consideración a tener en cuenta es que si se generan deadlines se estaría en un escenario análogo al de no tener restricciones. En caso de que los deadlines sean muy reducidos es probable que las instancias no tengan solución.\\
La evaluación para saber si dada una instancia existe una planificación cualquiera que satisfaga las restricciones es un problema complejo en sí. Por lo tanto se considera que los deadlines serán en principio bastante holgados.\\
Otro problema reconocido es el de factibilizar soluciones. Luego de obtenido el individuo, si este viola las restricciones de deadline pero tiene características que otorgan un buen makespan, es probable que si le aplico determinadas operaciones al mismo para tratar de que el deadline de todas las tareas se cumpla, consiga un individuo que me represente una buena solución (una operación es por ejemplo ordenar las tareas de una misma máquina por deadline, esto no modifica el makespan y en todo caso beneficia la violación de restricciones). Este algoritmo (corrector)  de factibilización de soluciones es una de las primeras implementaciones a realizar ya que se usará tanto en heurísticas al inicializar la población como en los operadores de los algoritmos.



\section{Esquema del Algoritmo Evolutivo}

\section{Configuración del Algoritmo Evolutivo}

En esta sección se explica la codificación del problema, la función de fitness y los operadores utilizados.

\subsection{Codificación del cromosoma}

Tradicionalmente en los problemas de scheduling se utilizan las codificaciones orientadas a tareas o a máquinas. Se optó por la segunda opción dado que la misma permite calcular con mayor facilidad el tiempo de finalización de una tarea, necesario para saber si se cumple o no el deadline.  En la codificación oriendada a tareas se puede agregar un campo que indique la posición relativa de la tarea dentro de la máquina pero lo consideramos a priori menos conveniente a la hora de realizar evaluaciones. 
Otro motivo para usar la codificación elegida es que permite aplicar fácilmente búsquedas locales que incluyan intercambios de tareas.

\subsection{Función de fitness}
De forma de que el problema sea efectivamente un problema de maximización se tomará como función de fitness el opuesto del makespan.

\subsection{Inicializar la población}

Para generar la población inicial se consideran diversas heurísticas que manejan las mismas ideas que Min-Min, Sufferage. La inicialización de la población tiene un costo no despreciable y no se descarta la implementación en paralelo.



\section{Algoritmos a utilizar}





Se realizaran dos algoritmos genéticos que comparten caracteristicas similares en sus operadores. Uno es el algoritmo genetico clásico y otro el CHC.\\

SGA: El algorimo genético clasico de Glorberg consta de un operador de cruzamiento de un punto (SPX), mutación probabilistica y selección de ruleta.\\

Llevados a la repesentación elegida, el SPX queda de la forma siguiente: Se elige un punto al azar y se intercambian las tareas (a partir de ese punto) de un padre por las correspondiente en el otro. En caso de que el progenitor no cumpla con los deadline intentará factibilizar por medio del algoritmo corrector. En caso de que no se logre, se sortea otro punto. Si no se consigue hacer válido al progenitor luego de un número de intentos no se realiza la sustitución y el padre forma parte de la próxima generación.\\ 

La mutación intenta proveer de diversidad genética a la población mediante una perturbación en un individuo. En este caso se trata del intercambio de tareas, elegidas aleatoriamente, pero orientada a mejorar el makespan por caminos que no se lograr\'ian solamente con el cruzamiento. El operador de mutación del SGA intercambiar\'a entonces dos tareas al azar, una de la máquina que finaliza primero, y otro de la máquina más lenta. Igual que en la selección en caso de que el resultado del operador no sea factible respecto a las restricciones, se aplicará el algoritmo corrector. \\

CHC (Cross  generation elistist selection, Heterogeneous recombination, and Cataclysmic mutation):
Es un algoritmo evolutivo elitista que utiliza cruzamiento uniforme, reinicialización de la población en lugar de mutación y restricciones de semejanza al momento de aplicar el cruzamiento.\\

El cruzamiennto uniforme en el CHC intercambia con probabilidad 0,5 las tareas de un padre por la correspondiente del otro, siempre que se cumpla la restricción de cruzamiento, esto es que los progenitores difieran entre sí un determinado umbral, que se decrementa cada vez que la población no cambie. Cuando el umbral llega a cero se interpreta que se ha convergido y se reinicia la población mediate el operador de mutación del SGA.\\

Al momento de reiniciar la población se considera tomar el mejor individuo y aplicandole el operdador de mutación para generar el resto o aplicar directamente el operador a los peores individuos.\\


\section{Framework}
La implementación de todos los algoritmos se realizará en C++, utilizando la biblioteca MALLBA.
Las implementaciones paralelas se harán con la biblioteca MPI.


\section{Experimentos a realizar y presentación de resultados}


Dado que no se encontró en la bibliografia revisada un trabajo anterior que considere el problema tal cual se consibe en este trabajo, el análisis sobre los resultados se hará entre los algorítmos implementados y las heurísticas. Como expectativa se maneja que el mejor resultado se obtenga con el CHC, luego el AG clásico y por último las heurísticas. También se pretende que las versiones paralelas superen a las seriales, si no en calidad de resultados, sí en los tiempos (esto se obtendrá del correspondiente análisis de las métricas como el speed up). 
Otro estudio a realizar es generar instancias de problema de tamaño reducido de forma que se pueda mediante un método exhaustivo encontrar la solución óptima, para comparar luego con la alcanzada con las heurísticas. Más allá que esto es una medida inequivoca de cuán buena es la solución alcanzada por el algoritmo, está lejos de ser la prueba más importante, porque el trabajo está a orientado a dimensiones realistas (por ejemplo va a existir un compromiso entre el tiempo de cómputo y la calidad de las soluciones que no tiene sentido en instancias reducidas del problema).
Hay publicados instancias del HSCP sin restricciones y los resultados alcanzados con distintos algoritmos. Se pretende complementar las instacias agregandoles el dealine y luego comparar que tanto se afecta el makespan. De ninguna forma se podrían mejor los tiempos pero el análisis resulta interesante y se podrán sacar algunas conclusiones sobre el comportamiento que podrían retroalimentar la implementación o la calibración. 



\nocite{*}
\bibliographystyle{IEEEtran}
\bibliography{HSCP_Bibliografia.bib}


\end{document}
